package data_structure;

public class leetcode_0109 {
    public TreeNode sortedListToBST(ListNode head) {
        TreeNode root = buildTree(head,null);
        return root;
    }

    private TreeNode buildTree(ListNode head, ListNode node) {
        if(head==node){
            return null;
        }
        ListNode midNode = midNode(head, node);
        TreeNode root = new TreeNode(midNode.val);
        root.left = buildTree(head,midNode);
        root.right = buildTree(midNode.next,node);
        return root;
    }

    private ListNode midNode(ListNode left,ListNode right){
        ListNode slow = left;
        ListNode fast = left;
        while(fast !=right && fast.next !=right){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}
